package fun.coding.leetcode;

public class UniquePathsII {

	public static void main(String[] args) {
		UniquePathsII up2 = new UniquePathsII();
		int[][] test = {
		                {0,0,0},
		                {0,1,0},
		                {0,0,0}
		};
		System.out.println(up2.uniquePathsWithObstacles(test));
	}
	
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    	int m = obstacleGrid.length;
    	int n = obstacleGrid[0].length;
    	
    	if (!(m >= 1 && n >= 1)) return 0;
    	
    	int[][] lookup = new int[m+1][n+1];
    	
    	for (int i = 1; i <= m; i++) {
    		for (int j = 1; j <= n; j++) {
    			if (obstacleGrid[i-1][j-1] != 1) {
    				lookup[i][j] = lookup[i-1][j] + lookup[i][j-1];
    				if (i == 1 && j == 1) lookup[i][j] = 1;
    			} else {
    				lookup[i][j] = 0;
    			}
    		}
    	}
    	return lookup[m][n];
    }

}
